Demodulation involves extracting an original information-bearing signal from a signal which is modulated in accordance with a particular constellation and transmitted over a channel. The complexity of the demodulation process increases significantly for very large signal constellations. Relatively large signal constellations such as 16-, 32- and 64-QAM (Quadrature Amplitude Modulation) have been adopted in EDGE (Enhanced Data Rates for GSM Evolution), HSPA (High Speed Packet Access), LTE (Long Term Evolution) and WiMax (Worldwide Interoperability for Microwave Access). In HSPA, multi-code transmission creates even larger effective constellations. Also, MIMO (Multiple-Input, Multiple-Output) schemes with two or more streams have been adopted in HSPA, LTE and WiMax. MIMO implementations also yield relatively large effective constellations. Demodulation complexity further increases when any of these techniques occur in combination, e.g. multi-code and MIMO.
The ideal demodulation scheme is MLD (Maximum Likelihood Detection). However, the complexity of MLD increases substantially due to the size of the modulation constellation and/or because of the exponential effects of MIMO or multi-codes to the point where MLD becomes impractical. Less complex solutions are available such as sphere decoding (SD), where the demodulator tries to approximate the performance of MLD, but limits its search for the best solution to a subset of all possible transmitted signals, and where the subset is described by a sphere. A key step in SD is the triangular factorization of the channel matrix. This step simplifies the identification of candidate solutions in the sphere.
Another conventional demodulation technique is ITS (Iterative Tree Search) detection for MIMO QAM. ITS can be viewed as an alternative to SD. Like SD, ITS exploits the triangular factorization of the channel. Unlike SD, ITS uses the M-algorithm for reducing the search for the best candidate. ITS breaks down the search further, by dividing the QAM constellation in its four quadrants, and representing each quadrant by its centroid in intermediate computations. The selected quadrant itself is subdivided again into its 4 quadrants, and so on. This results in a quaternary tree search. Other conventional approaches give particular attention to the additional error introduced by the use of the centroids instead of true symbols. The error is modeled as Gaussian noise whose variance is determined and incorporated in likelihood computations. However, a tight connection is typically made between the centroid representation and the bit mapping from bits to symbols. That is, if a so-called multi-level bit mapping is employed, then identifying a quadrant is equivalent to making a decision on a certain pair of bits. Such constraints place a restriction on bit mappings, restricting the design of subsets.